
Adapting cost%2Dsensitive learning for reject option.

Asking Generalized Queries to Ambiguous Oracle.

Supervised Learning with Minimal Effort.

A real%2Dcoded biogeography%2Dbased optimization with mutation.

Asking Generalized Queries to Domain Experts to Improve Learning.
Abstract—With the assistance of a domain expert, active learning can often select or construct fewer examples to request their labels to build an accurate classifier. However, previous works of active learning can only generate and ask specific queries. In real-world applications, the domain experts (or oracles) are often more readily to answer “generalized queries ” with don’t-care attributes. The power of such generalized queries is that one generalized query is often equivalent to many specific ones. However, overly general queries are not good as answers from the domain experts (or oracles) can be highly uncertain, and this makes learning difficult. In this paper, we propose a novel active learning algorithm that asks good generalized queries. We then extend our algorithm to construct new, hierarchical features for both nominal and numeric attributes. We demonstrate experimentally that, our new method asks significantly fewer queries compared with the previous works of active learning, even when the initial labeled dataset is very small, and the oracle is inaccurate in class probability estimations. Our method can be readily deployed in real-world data mining tasks where obtaining labeled examples is costly. This is an extension of the paper published in IEEE ICDM 2009 [16]. Keywords—active learning, domain expert, generalized query. 1
Co%2DTraining on Handwritten Digit Recognition.

Co%2DTraining on Handwritten Digit Recognition.

Hybrid differential evolution based on fuzzy C%2Dmeans clustering.

Hybrid differential evolution based on fuzzy C%2Dmeans clustering.

Active Learning with Generalized Queries.
Abstract—Active learning can actively select or construct examples to label to reduce the number of labeled examples needed for building accurate classifiers. However, previous works of active learning can only ask specific queries. For example, to predict osteoarthritis from a patient dataset with 30 attributes, specific queries always contain values of all these 30 attributes, many of which may be irrelevant. A more natural way is to ask “generalized queries ” with don’t-care attributes, such as “are people over 50 with knee pain likely to have osteoarthritis? ” (with only two attributes: age and type of pain). We assume that the oracle (and human experts) can readily answer those generalized queries by returning probabilistic labels. The power of such generalized queries is that one generalized query may be equivalent to many specific ones. However, overly general queries may receive highly uncertain labels from the oracle, and this makes learning difficult. In this paper, we propose a novel active learning algorithm that asks generalized queries. We demonstrate experimentally that our new method asks significantly fewer queries compared with the previous works of active learning. Our method can be readily deployed in real-world tasks where obtaining labeled examples is costly. Keywords-active learning, generalized queries, supervised learning. I.
When does Co%2Dtraining Work in Real Data%3F.
Abstract—Co-training, a paradigm of semi-supervised learning, is promised to alleviate effectively the shortage of labeled examples in supervised learning. The standard two-view co-training requires the dataset to be described by two views of features, and previous studies have shown that co-training works well if the two views satisfy the sufficiency and independence assumptions. In practice, however, these two assumptions are often not known or ensured (even when the two views are given). More commonly, most supervised datasets are described by one set of attributes (one view). Thus, they need be split into two views in order to apply the standard twoview co-training. In this paper, we first propose a novel approach to empirically verify the two assumptions of co-training given two views. Then, we design several methods to split single view datasets into two views, in order to make co-training work reliably well. Our empirical results show that, given a whole or a large labeled training set, our view verification and splitting methods are quite effective. Unfortunately, co-training is called for precisely when the labeled training set is small. However, given small labeled training sets, we show that the two co-training assumptions are difficult to verify, and view splitting is unreliable. Our conclusions for co-training’s effectiveness are mixed. If two views are given, and known to satisfy the two assumptions, co-training works well. Otherwise, based on small labeled training sets, verifying the assumptions or splitting single view into two views are unreliable, thus it is uncertain whether the standard co-training would work or not.
Semi%2DSupervised Learning in Reconstructed Manifold Space for 3D Caricature Generation.

Advanced Data Mining and Applications
Advanced Data Mining applications require more and more support from relational database engines. Especially clustering applications in high dimensional features space demand a proper support of multiple Top-k queries in order to perform projected clustering. Although some research tackles to problem of optimizing restricted ranking (top-k) queries, there is no solution considering more than one single ranking criterion. This deficit- optimizing multiple Topk queries over joins- is targeted by this paper from two perspectives. On the one hand, we propose a minimal but quite handy extension of SQL to express multiple top-k queries. On the other hand, we propose an optimized hash join strategy to efficiently execute this type of queries. Extensive experiments conducted in this context show the feasibility of our proposal. 1.
Semi%2Dsupervised Self%2Dtraining for Sentence Subjectivity Classification.

Proper Model Selection with Significance Test.
Abstract. Model selection is an important and ubiquitous task in machine learning. To select models with the best future classification performance measured by a goal metric, anevaluation metric is often used to select the best classification model among the competing ones. A common practice is to use the same goal and evaluation metric. However, in several recent studies, it is claimed that using an evaluation metric (such as AUC) other than the goal metric (such as accuracy) results in better selection of the correct models. In this paper, we point out a flaw in the experimental design of those studies, and propose an improved method to test the claim. Our extensive experiments show convincingly that only the goal metric itself can most reliably select the correct classification models. 1
Discriminative parameter learning for Bayesian networks.
Bayesian network classifiers have been widely used for classification problems. Given a fixed Bayesian network structure, parameters learning can take two different approaches: generative and discriminative learning. While generative parameter learning is more efficient, discriminative parameter learning is more effective. In this paper, we propose a simple, efficient, and effective discriminative parameter learning method, called Discriminative Frequency Estimate (DFE), which learns parameters by discriminatively computing frequencies from data. Empirical studies show that the DFE algorithm integrates the advantages of both generative and discriminative learning: it performs as well as the state-of-the-art discriminative parameter learning method ELR in accuracy, but is significantly more efficient. 1.
Active learning with direct query construction.
Active learning may hold the key for solving the data scarcity problem in supervised learning, i.e., the lack of labeled data. Indeed, labeling data is a costly process, yet an active learner may request labels of only selected instances, thus reducing labeling work dramatically. Most previous works of active learning are, however, pool-based; that is, a pool of unlabelled examples is given and the learner can only select examples from the pool to query for their labels. This type of active learning has several weaknesses. In this paper we propose novel active learning algorithms that construct examples directly to query for labels. We study both a specific active learner based on the decision tree algorithm, and a general active learner that can work with any base learning algorithm. As there is no restriction on what examples to be queried, our methods are shown to often query fewer examples to reduce the predictive error quickly. This casts doubt on the usefulness of the pool in pool-based active learning. Nevertheless, our methods can be easily adapted to work with a given pool of unlabeled examples.
Active learning with direct query construction.
Active learning may hold the key for solving the data scarcity problem in supervised learning, i.e., the lack of labeled data. Indeed, labeling data is a costly process, yet an active learner may request labels of only selected instances, thus reducing labeling work dramatically. Most previous works of active learning are, however, pool-based; that is, a pool of unlabelled examples is given and the learner can only select examples from the pool to query for their labels. This type of active learning has several weaknesses. In this paper we propose novel active learning algorithms that construct examples directly to query for labels. We study both a specific active learner based on the decision tree algorithm, and a general active learner that can work with any base learning algorithm. As there is no restriction on what examples to be queried, our methods are shown to often query fewer examples to reduce the predictive error quickly. This casts doubt on the usefulness of the pool in pool-based active learning. Nevertheless, our methods can be easily adapted to work with a given pool of unlabeled examples.
Cost%2DSensitive Decision Trees with Pre%2Dpruning.

Cost%2DSensitive Decision Trees with Pre%2Dpruning.





A Multi%2DObjective Genetic Algorithm Based on Density.

Machine learning for stock selection.

Partial example acquisition in cost%2Dsensitive learning.

Extracting Actionable Knowledge from Decision Trees.
Abstract—Most data mining algorithms and tools stop at discovered customer models, producing distribution information on customer profiles. Such techniques, when applied to industrial problems such as customer relationship management (CRM), are useful in pointing out customers who are likely attritors and customers who are loyal, but they require human experts to postprocess the discovered knowledge manually. Most of the postprocessing techniques have been limited to producing visualization results and interestingness ranking, but they do not directly suggest actions that would lead to an increase in the objective function such as profit. In this paper, we present novel algorithms that suggest actions to change customers from an undesired status (such as attritors) to a desired one (such as loyal) while maximizing an objective function: the expected net profit. These algorithms can discover costeffective actions to transform customers from undesirable classes to desirable ones. The approach we take integrates data mining and decision making tightly by formulating the decision making problems directly on top of the data mining results in a postprocessing step. To improve the effectiveness of the approach, we also present an ensemble of decision trees which is shown to be more robust when the training data changes. Empirical tests are conducted on both a realistic insurance application domain and UCI benchmark data. Index Terms—Phrases decision making, data mining, machine learning. 1
Customized classification learning based on query projections.

Cost%2DSensitive Test Strategies.
In medical diagnosis doctors must often determine what medical tests (e.g., X-ray, blood tests) should be ordered for a patient to minimize the total cost of medical tests and misdiagnosis. In this paper, we design cost-sensitive machine learning algorithms to model this learning and diagnosis process. Medical tests are like attributes in machine learning whose values may be obtained at cost (attribute cost), and misdiagnoses are like misclassifications which may also incur a cost (misclassification cost). We first propose an improved decision tree learning algorithm that minimizes the sum of attribute costs and misclassification costs. Then we design several novel “test strategies ” that may request to obtain values of unknown attributes at cost (similar to doctors ’ ordering of medical tests at cost) in order to minimize the total cost for test examples (new patients). We empirically evaluate and compare these test strategies, and show that they are effective and that they outperform previous methods. A case study on heart disease is given.
Thresholding for Making Classifiers Cost%2Dsensitive.

ODE A Fast and Robust Differential Evolution Based on Orthogonal Design.

Keyphrase Extraction Using Semantic Networks Structure Analysis.
Keyphrases play a key role in text indexing, summarization, and categorization. However, most of the existing keyphrase extraction approaches require human-labeled training sets. In this paper, we propose an automatic keyphrase extraction algorithm using two novel feature weights, which can be used in both supervised and unsupervised tasks. This algorithm treats each document as a semantic network that holds both syntactic and statistical information. Structural dynamics of these networks can easily identify key nodes, which can be used to extract keyphrases unsupervisedly. Experiments demonstrate the proposed keyphrase extraction algorithm averagely improves 50 % in effectiveness and 30 % in efficiency in unsupervised tasks and performs comparatively with supervised extractors. Moreover, by applying this algorithm to supervised task, we develop a more accurate classifier. In this classifier, we assemble several syntactic and statistical features. Experiments show that the overall precision of supervised extraction can be up to 80%. 1.
Constructing Ensembles for Better Ranking.

Feature value acquisition in testing a sequential batch test algorithm.
In medical diagnosis, doctors often have to order sets of medical tests in sequence in order to make an accurate diagnosis of patient diseases. While doing so they have to make a trade-off between the cost of the tests and possible misdiagnosis. In this paper, we use cost-sensitive learning to model this process. We assume that test examples (new patients) may contain missing values, and their actual values can be acquired at cost (similar to doing medical tests) in order to reduce misclassification errors (misdiagnosis). We propose a novel Sequential Batch Test algorithm that can acquire sets of attribute values in sequence, similar to sets of medical tests ordered by doctors in sequence. The goal of our algorithm is to minimize the total cost (i.e., the trade-off) of acquiring attribute values and misclassifications. We demonstrate the effectiveness of our algorithm, and show that it outperforms previous methods significantly. Our algorithm can be readily applied in real-world diagnosis tasks. A case study on the heart disease is given in the paper. 1.
Maximum profit mining and its application in software development.
While most software defects (i.e., bugs) are corrected and tested as part of the lengthy software development cycle, enterprise software vendors often have to release software products before all reported defects are corrected, due to deadlines and limited resources. A small number of these defects will be escalated by customers and they must be resolved immediately by the software vendors at a very high cost. In this paper, we develop an Escalation Prediction (EP) system that mines historic defect report data and predict the escalation risk of the defects for maximum net profit. More specifically, we first describe a simple and general framework to convert the maximum net profit problem to cost-sensitive learning. We then apply and compare several well-known cost-sensitive learning approaches for EP. Our experiments suggest that the cost-sensitive decision tree is the best method for producing the highest positive net profit and comprehensible results. The EP system has been deployed successfully in the product group of an enterprise software vendor. (Note: this paper is accepted by KDD’06)
IndexToolkit an open source toolbox to index protein databases for high%2Dthroughput proteomics.

Discovering Classification from Data of Multiple Sources.
Abstract. In many large e-commerce organizations, multiple data sources are often used to describe the same customers, thus it is important to consolidate data of multiple sources for intelligent business decision making. In this paper, we propose a novel method that predicts the classification of data from multiple sources without class labels in each source. We test our method on artificial and real-world datasets, and show that it can classify the data accurately. From the machine learning perspective, our method removes the fundamental assumption of providing class labels in supervised learning, and bridges the gap between supervised and unsupervised learning.
Learning Contextual Dependency Network Models for Link%2DBased Classification.
Links among objects contain rich semantics that can be very helpful in classifying the objects. However, many irrelevant links can be found in real-world link data such as Web pages. Often, these noisy and irrelevant links do not provide useful and predictive information for categorization. It is thus important to automatically identify which links are most relevant for categorization. In this paper, we present a contextual dependency network (CDN) model for classifying linked objects in the presence of noisy and irrelevant links. The CDN model makes use of a dependency function that characterizes the contextual dependencies among linked objects. In this way, CDNs can differentiate the impacts of the related objects on the classification and consequently reduce the effect of irrelevant links on the classification. We show how to learn the CDN model effectively and how to use the Gibbs inference framework over the learned model for collective classification of multiple linked objects. The experiments show that the CDN model demonstrates relatively high robustness on data sets containing irrelevant links.
Test%2DCost Sensitive Classification on Data with Missing Values.
 In the area of cost-sensitive learning, inductive learning algorithms have been extended to handle different types of costs to better represent misclassification errors. Most of the previous works have only focused on how to deal with misclassification costs. In this paper, we address the equally important issue of how to handle the test costs associated with querying the missing values in a test case. When an attribute contains a missing value in a test case, it may or may not be worthwhile to take the extra effort in order to obtain a value for that attribute, or attributes, depending on how much benefit the new value will bring about in increasing the accuracy. In this paper, we consider how to integrate test-cost-sensitive learning with the handling of missing values in a unified framework that includes model building and a testing strategy. The testing strategies determine which attributes to perform the test on in order to minimize the sum of the classification costs and test costs. We show how to instantiate this framework in two popular machine learning algorithms: decision trees and naive Bayesian method. We empirically evaluate the test-cost-sensitive methods for handling missing values on several data sets. 
Test Strategies for Cost%2DSensitive Decision Trees.
Abstract. We study cost-sensitive learning of decision trees that incorporate both test costs and misclassification costs. In particular, we first propose a lazy decision tree learning that minimizes the total cost of tests and misclassifications. Then assuming test examples may contain unknown attributes whose values can be obtained at a cost (the test cost), we design several novel test strategies which attempt to minimize the total cost of tests and misclassifications for each test example. We empirically evaluate our treebuilding and various test strategies, and show that they are very effective. Our results can be readily applied to real-world diagnosis tasks, such as medical diagnosis where doctors must try to determine what tests (e.g., blood tests) should be ordered for a patient to minimize the total cost of tests and misclassifications (misdiagnosis). A case study on heart disease is given throughout the paper. 1
Simple Test Strategies for Cost%2DSensitive Decision Trees.
Abstract. We study cost-sensitive learning of decision trees that incorporate both test costs and misclassification costs. In particular, we first propose a lazy decision tree learning that minimizes the total cost of tests and misclassifications. Then assuming test examples may contain unknown attributes whose values can be obtained at a cost (the test cost), we design several novel test strategies which attempt to minimize the total cost of tests and misclassifications for each test example. We empirically evaluate our treebuilding and various test strategies, and show that they are very effective. Our results can be readily applied to real-world diagnosis tasks, such as medical diagnosis where doctors must try to determine what tests (e.g., blood tests) should be ordered for a patient to minimize the total cost of tests and misclassifications (misdiagnosis). A case study on heart disease is given throughout the paper. 1
Partial Ensemble Classifiers Selection for Better Ranking.

Predicting Software Escalations with Maximum ROI.
Enterprise software venders often have to release software products before all reported defects are corrected, and a small number of these reported defects will be escalated by customers whose businesses are seriously impacted. Escalated defects must be quickly resolved at a high cost by the software vendors. The total costs can be even greater, including loss of reputation, satisfaction, loyalty, and repeat revenue. In this paper, we develop an Escalation Prediction (EP) system to mine historic defect report data and predict the escalation risk of current defect reports for maximum ROI (Return On Investment). More specifically, we first describe a simple and general framework to convert the maximum ROI problem to cost-sensitive learning. We then apply and compare several best-known cost-sensitive learning approaches for EP. The EP system has produced promising results, and has been deployed in the product group of an enterprise software vendor. Conclusions drawn from this study also provide guidelines for mining imbalanced datasets and costsensitive learning. 1.
Hybrid Cost%2DSensitive Decision Tree.
Abstract. Cost-sensitive decision tree and cost-sensitive naïve Bayes are both new cost-sensitive learning models proposed recently to minimize the total cost of test and misclassifications. Each of them has its advantages and disadvantages. In this paper, we propose a novel cost-sensitive learning model, a hybrid cost-sensitive decision tree, called DTNB, to reduce the minimum total cost, which integrates the advantages of cost-sensitive decision tree and of the cost-sensitive naïve Bayes together. We empirically evaluate it over various test strategies, and our experiments show that our DTNB outperforms cost-sensitive decision and the cost-sensitive naïve Bayes significantly in minimizing the total cost of tests and misclassification based on the same sequential test strategies, and single batch strategies. 1
Rank Measures for Ordering.
Abstract. Many data mining applications require a ranking, rather than a mere classification, of cases. Examples of these applications are widespread, including Internet search engines (ranking of pages returned) and customer relationship management(ranking of profitable customers). However,little theoretical foundation and practical guideline have been established to assess the merits of different rank measures for ordering. In this paper, we first review several general criteria to judge the merits of different single-number measures. Then we propose a novel rank measure, and compare the commonly used rank measures and our new one according to the criteria. This leads to a preference order for these rank measures. We conduct experiments on real-world datasets to confirm the preference order. The results of the paper will be very useful in evaluating and comparing rank algorithms.
Dynamic Ensemble Re%2DConstruction for Better Ranking.
Abstract. Ensemble learning has been shown to be very successful in data mining. However most work on ensemble learning concerns the task of classification. Little work has been done to construct ensembles that aim to improve ranking. In this paper, we propose an approach to re-construct new ensembles based on a given ensemble with the purpose to improve the ranking performance, which is crucial in many data mining tasks. The experiments with real-world data sets show that our new approach achieves significant improvements in ranking over the original Bagging and Adaboost ensembles. 1
pFind a novel database%2Dsearching software system for automated peptide and protein identification via tandem mass spectrometry.

%22Missing Is Useful%27 Missing Values in Cost%2DSensitive Decision Trees.
Abstract—Many real-world data sets for machine learning and data mining contain missing values and much previous research regards it as a problem and attempts to impute missing values before training and testing. In this paper, we study this issue in costsensitive learning that considers both test costs and misclassification costs. If some attributes (tests) are too expensive in obtaining their values, it would be more cost-effective to miss out their values, similar to skipping expensive and risky tests (missing values) in patient diagnosis (classification). That is, “missing is useful ” as missing values actually reduces the total cost of tests and misclassifications and, therefore, it is not meaningful to impute their values. We discuss and compare several strategies that utilize only known values and that “missing is useful ” for cost reduction in cost-sensitive decision tree learning. Index Terms—Induction, knowledge acquisition, machine learning. 1
Using AUC and Accuracy in Evaluating Learning Algorithms %2D Appendices.

Using AUC and Accuracy in Evaluating Learning Algorithms.
The area under the ROC (Receiver Operating Characteristics) curve, or simply AUC, has been recently proposed as an alternative single-number measure for evaluating the predictive ability of learning algorithms. However, no formal arguments were given as to why AUC should be preferred over accuracy. In this paper, we establish formal criteria for comparing two different measures for learning algorithms, and we show theoretically and empirically that AUC is, in general, a better measure (defined precisely) than accuracy. We then reevaluate well-established claims in machine learning based on accuracy using AUC, and obtain interesting and surprising new results. We also show that AUC is more directly associated with the net profit than accuracy in direct marketing, suggesting that learning algorithms should optimize AUC instead of accuracy in real-world applications. The conclusions drawn in this paper may make a significant impact to machine learning and data mining applications. Note: This paper integrates results in our papers published in IJCAI 2003 [22] and ICDM 2003 [15]. It also includes many new results. For example, the concept of indifferency in Section II-B is new, and Sections III-B, III-C, IV-A, IV-D, and V are all new and unpublished. Index Terms Evaluation of learning algorithms, AUC vs accuracy, ROC
Guest Editors%27 Introduction to the Special Issue Machine Learning for Bioinformatics %2D Part 1.

Guest Editor%27s Introduction to the Special Issue Machine Learning for Bioinformatics%2DPart 2.

A Multi%2Dobjective Genetic Algorithm Based on Quick Sort.

Artificial Aging of Faces by Support Vector Machines.

Test%2DCost Sensitive Naive Bayes Classification.
Inductive learning techniques such as the naive Bayes and decision tree algorithms have been extended in the past to handle different types of costs mainly by distinguishing different costs of classification errors. However, it is an equally important issue to consider how to handle the test costs associated with querying the missing values in a test case. When the value of an attribute is missing in a test case, it may or may not be worthwhile to take the effort to obtain its missing value, depending on how much the value will result in a potential gain in the classification accuracy. In this paper, we show how to obtain a test-cost sensitive naive Bayes classifier (csNB) by including a test strategy which determines how unknown attributes are selected to perform test on in order to minimize the sum of the misclassification costs and test costs. We propose and evaluate several potential test strategies including one that allows several tests to be done at once. We empirically evaluate the csNB method, and show that it compares favorably with its decision tree counterpart. 1.
Decision trees with minimal costs.
We propose a simple, novel and yet effective method for building and testing decision trees that minimizes the sum of the misclassification and test costs. More specifically, we first put forward an original and simple splitting criterion for attribute selection in tree building. Our treebuilding algorithm has many desirable properties for a cost-sensitive learning system that must account for both types of costs. Then, assuming that the test cases may have a large number of missing values, we design several intelligent test strategies that can suggest ways of obtaining the missing values at a cost in order to minimize the total cost. We experimentally compare these strategies and C4.5, and demonstrate that our new algorithms significantly outperform C4.5 and its variations. In addition, our algorithm’s complexity is similar to that of C4.5, and is much lower than that of previous work. Our work is useful for many diagnostic tasks which must factor in the misclassification and test costs for obtaining missing information. 1.
A New Method to Construct the Non%2DDominated Set in Multi%2DObjective Genetic Algorithms.

A Kernel%2DBased Case Retrieval Algorithm with Application to Bioinformatics.

Exploiting the kernel trick to correlate fragment ions for peptide identification via tandem mass spectrometry.
Motivation: The correlation among fragment ions in a tandem mass spectrum is crucial in reducing stochastic mismatches for peptide identification by database searching. Until now, an efficient scoring algorithm that considers the correlative information in a tunable and comprehensive manner has been lacking. Results: This paper provides a promising approach to utilizing the correlative information for improving the peptide identification accuracy.The kernel trick, rooted in the statistical learning theory, is exploited to address this issue with low computational effort. The common scoring method, the tandem mass spectral dot product (SDP), is extended to the kernel SDP (KSDP). Experiments on a dataset reported previously demonstrate the effectiveness of the KSDP.The implementation on consecutive fragments shows a decrease of 10 % in the error rate compared with the SDP. Our software tool, pFind, using a simple scoring function based on the KSDP, outperforms two SDPbased software tools, SEQUEST and Sonar MS/MS, in terms of identification accuracy. 
AUC A Better Measure than Accuracy in Comparing Learning Algorithms.
Predictive accuracy has been widely used as the main criterion  for comparing the predictive ability of classification systems (such  as C4.5, neural networks, and Naive Bayes). Most of these classifiers also  produce probability estimations of the classification, but they are completely  ignored in the accuracy measure. This is often taken for granted  because both training and testing sets only provide class labels. In this  paper we establish rigourously that, even in this setting, the area under  the ROC (Receiver Operating Characteristics) curve, or simply AUC,  provides a better measure than accuracy. Our result is quite significant  for three reasons. First, we establish, for the first time, rigourous  criteria for comparing evaluation measures for learning algorithms. Second,  it suggests that AUC should replace accuracy when measuring and  comparing classification systems. Third, our result also prompts us to  re-evaluate many well-established conclusions based on accuracy in machine  learning. For example, it is well accepted in the machine learning  community that, in terms of predictive accuracy, Naive Bayes and decision  trees are very similar. Using AUC, however, we show experimentally  that Naive Bayes is significantly better than the decision-tree learning  algorithms.
A Fundamental Issue of Naive Bayes.
Naive Bayes is one of the most efficient and effective inductive learning algorithms for machine learning and data mining. But the conditional independence assumption on which it is based, is rarely true in real-world applications. Researchers extended naive Bayes to represent dependence explicitly, and proposed related learning algorithms based on dependence. In this paper, we argue that, from the classification point of view, dependence distribution plays a crucial role, rather than dependence. We propose a novel explanation on the superb classification performance of naive Bayes. To verify our idea, we design and conduct experiments by extending the Chow-Liu algorithm to use the dependence distribution to construct TAN, instead of using mutual information that only reflects the dependencies among attributes. The empirical results provide evidences to support our new explanation.
Comparing Naive Bayes%2C Decision Trees%2C and SVM with AUC and Accuracy.
The predictive ability of a classification algorithm is typ-ically measured by its predictive accuracy (or error rate, which is 1 minus the accuracy) on the testing examples.Most classifiers (including C4.5 and Naive Bayes) can also produce probability estimations or &#034;confidence &#034; of the classprediction. Unfortunately, this information is completely ignored in accuracy.
Postprocessing Decision Trees to Extract Actionable Knowledge.
Most data mining algorithms and tools stop at discovered customer models, producing distribution information on customer profiles. Such techniques, when applied to industrial problems such as customer relationship management (CRM), are useful in pointing out customers who are likely attritors and customers who are loyal, but they require human experts to postprocess the mined information manually. Most of the postprocessing techniques have been limited to producing visualization results and interestingness ranking, but they do not directly suggest actions that would lead to an increase the objective function such as profit. In this paper, we present a novel algorithm that suggest actions to change customers from an undesired status (such as attritors) to a desired one (such as loyal) while maximizing objective function: the expected net profit. We develop these algorithms under resource constraints that are abound in reality. The contribution of the work is in taking the output from an existing mature technique (decision trees, for example), and producing novel, actionable knowledge through automatic postprocessing. 1.
Decision Tree with Better Ranking.
AUC (Area Under the Curve) of ROC (Receiver  Operating Characteristics) has been  recently used as a measure for ranking performance  of learning algorithms. In this paper,  we present a novel probability estimation  algorithm that improves the AUC value  of decision trees. Instead of estimating the  probability at the single leaf where the example  falls into, our method averages probability  estimates from all leaves of the tree.
AUC a Statistically Consistent and more Discriminating Measure than Accuracy.
Predictive accuracy has been used as the main and often only evaluation criterion for the predictive performance of classification learning algorithms. In recent years, the area under the ROC (Receiver Operating Characteristics) curve, or simply AUC, has been proposed as an alternative single-number measure for evaluating learning algorithms. In this paper, we prove that AUC is a better measure than accuracy. More specifically, we present rigourous definitions on consistency and discriminancy in comparing two evaluation measures for learning algorithms. We then present empirical evaluations and a formal proof to establish that AUC is indeed statistically consistent and more discriminating than accuracy. Our result is quite significant since we formally prove that, for the first time, AUC is a better measure than accuracy in the evaluation of learning algorithms. 1
Intelligent Protein 3D Structure Retrieval System.



Mining Optimal Actions for Profitable CRM.
Data mining has been applied to CRM (Customer Relationship Management) in many industries witha limited success. Most data mining tools can only discover customer models or profiles (such as customers who are likely attritors and customers who are loyal), but not actions that would improve customer relationship (such as changing attritors to loyal customers). We describe a novel algorithm that suggests actions to change customers from an undesired status (such as attritors) to a desired one (such as loyal). Our algorithm takes into account the cost of actions, and further, it attempts to maximize the expected net profit. To our best knowledge, no data miningalgorithmsor tools today can accomplish this important task in CRM. The algorithm is implemented, with many advanced features, in a specialized and highly effective data mining software called Proactive Solution.
Representational Upper Bounds of Bayesian Networks.
One of the fundamental issues of Bayesian  networks is their representational power, reflecting  what kind of functions they can or  cannot represent. In this paper, we first  prove an upper bound on the representational  power of Augmented Naive Bayes. We then  extend the result to general Bayesian networks.
Toward Bayesian Classifiers with Accurate Probabilities.
In most data mining applications, accurate ranking and probability estimation are essential. However, many traditional classifiers aim at a high classification accuracy (or low error rate) only, even though they also produce probability estimates. Does high predictive accuracy imply a better ranking and probability estimation? Is there any better evaluation method for those classifiers than the classification accuracy, for the purpose of data mining applications? The answer is the area under the ROC (Receiver Operating Characteristics) curve, or simply AUC.
Improving Encarta Search Engine Performance by Mining User Logs.

Editorial Notes.

Learning Prosodic Patterns for Mandarin Speech Synthesis.
Duminda Wijesekera and Daniel Barbara  15:00-16:00 Session 4 (Discussion)  . 15:00-15:15 Variations on Multimedia Data Mining Simeon J. Simoff  . 15:15-16:00 Discussion: What does Multimedia Mining encompass and what are the open issues  16:00-16:30 Coffee break  16:30 - 19:00 SIGKDD&#039;2000 Conference Opening and awards  viii  ix  Table of Contents  Geo-Spatial Clustering with User-Specified Constraints Anthony K.H. Tong, Raymond T. Ng, Laks V.S. Lakshmanan, Jiawei Han ...................... 1 Multi-level Indexing and GIS Enhanced Learning for Satellite Imageries Krzysztof Koperski, Giovanni B. Marchisio ............................................................8 Predicting Locations Using Map Similarity(PLUMS): A Framework for Spatial Data Mining. Sanjay Chawla, Shashi Shekhar, Weili Wu, Uygar Ozesmi ..........................................14 Learning Prosodic Patterns for Mandarin Speech Synthesis Yiqiang Chen, Wen Gao, Tingshao Zhu ..................................................
The Representational Power of Discrete Bayesian Networks.
One of the most important fundamental properties of Bayesian networks is the representational power, reflecting what kind of functions they can or cannot represent. In this paper, we establish an association between the structural complexity of Bayesian networks and their representational power. We use the maximum number of nodes ’ parents as the measure for the structural complexity of Bayesian networks, and the maximum XOR contained in a target function as the measure for the function complexity. A representational upper bound is established and proved. Roughly speaking, discrete Bayesian networks with each node having at most k parents cannot represent any function containing (k + 1)-XORs. Our theoretical results help us to gain a deeper understanding on the capacities and limitations of Bayesian networks.
Learning good prototypes for classification using filtering and abstraction of instances.

Geometric Properties of Naive Bayes in Nominal Domains.
Numerous approaches to learning classifiers, such as decision trees, neural networks, and instance-based learning, have been studied. In recent years, probability approaches to learning classifiers have been extensively investigated. According to Bayes Theorem, the probability of an example E = (a1; a2; \Delta \Delta \Delta; an) being in class c is
Mining Generalized Query Patterns from Web Logs.
User logs of a popular search engine keep track of user activities including user queries, user click-through from the returned list, and user browsing behaviors. Knowledge about user queries discovered from user logs can improve the performance of the search engine. We propose a data-mining approach that produces generalized query patterns or templates from the raw user logs of a popular commercial knowledge-based search engine that is currently in use. Our simulation shows that such templates can improve search engine&#039;s speed and precision, and can cover queries not asked previously. The templates are also comprehensible so web editors can easily discover topics in which most users are interested. 1. Introduction Data mining is a process of discovering implicit and useful knowledge from large datasets [Fayyad, et al, 1996]. Knowledge about datasets can be as simple as statistical information such as means and deviations, but data mining aims at finding higher level or more powerful...
Learnability of Augmented Naive Bayes in Nonimal Domains.

Data Mining for Direct Marketing Problems and Solutions.
Direct marketing is a process of identifying likely buyers  of certain products and promoting the products accordingly.
An Improved Learning Algorithm for Augmented Naive Bayes.
. Data mining applications require learning algorithms to have  high predictive accuracy, scale up to large datasets, and produce comprehensible  outcomes. Naive Bayes classifier has received extensive attention  due to its efficiency, reasonable predictive accuracy, and simplicity. However,  the assumption of attribute dependency given class of Naive Bayes  is often violated, producing incorrect probability that can affect the success  of data mining applications. We extend Naive Bayes classifier to  allow certain dependency relations among attributes. Comparing to previous  extensions of Naive Bayes, our algorithm is more efficient (more  so in problems with a large number of attributes), and produces simpler  dependency relation for better comprehensibility, while maintaining very  similar predictive accuracy.  1 
The Learnability of Naive Bayes.
Naive Bayes is an efficient and effective learning algorithm, but previous results show that its representation ability is severely limited since it can only represent certain linearly separable functions in the binary domain. We give necessary and sufficient conditions on linearly separable functions in the binary domain to be learnable by Naive Bayes under uniform representation. We then show that the learnability (and error rates) of Naive Bayes can be affected dramatically by sampling distributions. Our results help us to gain a much deeper understanding of this seemingly simple, yet powerful learning algorithm.
Grapheme Generation in Learning to Read English Words.

Data Mining for Direct Marketing Problems and Solutions.
Direct marketing is a process of identifying likely buyers  of certain products and promoting the products accordingly.
Computational Cognitive Modeling%2C the Source of Power%2C and Other Related Issues.

Alignment Algorithms for Learning to Read Aloud.

Computing Optimal Attribute Weight Settings for Nearest Neighbor Algorithms.

Learning Classifications from Multiple Sources of Unsupervised Data.

A Decision%2DTree Model of Balance Scale Development.
. We present an alternative model of human cognitive development on the balance scale task. Study of this task has inspired a wide range of human and computational work. The task requires that children predict the outcome of placing a discrete number of weights at various distances on either side of a fulcrum. Our model, which features the symbolic learning algorithm C4.5 as a transition mechanism, exhibits regularities found in the human data including orderly stage progression, U-shaped development, and the torque difference effect. Unlike previous successful models of the task, the current model uses a single free parameter, is not restricted in the size of the balance scale that it can accommodate, and does not require the assumption of a highly structured output representation or a training environment biased towards weight or distance information. The model makes a number of predictions differing from those of previous computational efforts.  Keywords: Cognitive development, bala...
Overfitting and generalization in learning discrete patterns.

Inverting Implication with Small Training Sets.
. We present an algorithm for inducing recursive clauses using inverse implication (rather than inverse resolution) as the underlying generalization method. Our approach applies to a class of logic programs similar to the class of primitive recursive functions. Induction is performed using a small number of positive examples that need not be along the same resolution path. Our algorithm, implemented in a system named CRUSTACEAN, locates matched lists of generating terms that determine the pattern of decomposition exhibited in the (target) recursive clause. Our theoretical analysis defines the class of logic programs for which our approach is complete, described in terms characteristic of other ILP approaches. Our current implementation is considerably faster than previously reported. We present evidence demonstrating that, given randomly selected inputs, increasing the number of positive examples increases accuracy and reduces the number of outputs. We relate our approach to similar re...
Learning Recursive Relations with Randomly Selected Small Training Sets.
We evaluate CRUSTACEAN, an inductive logic programming algorithm that uses inverse implication to induce recursive clauses from examples. This approach is well suited for learning a class of self-recursive clauses, which commonly appear in logic programs, because it searches for common substructures among the examples. However, little evidence exists that inverse implication approaches perform well when given only randomly selected positive and negative examples. We show that CRUSTACEAN  learns recursive relations with higher accuracies than GOLEM, yet with reasonable efficiency. We also demonstrate that increasing the number of randomly selected positive and negative examples increases its accuracy on randomly selected test examples, increases the frequency in which it outputs the target relation, and reduces its number of outputs. We also prove a theorem that defines the class of logic programs for which our approach is complete. 1 MOTIVATION  This paper extends our previous work (Ah...
Learning the Past Tense of English Verbs The Symbolic Pattern Associator vs. Connectionist Models
Learning the past tense of English verbs --- a seemingly minor aspect of language acquisition  --- has generated heated debates since 1986, and has become a landmark task  for testing the adequacy of cognitive modeling. Several artificial neural networks (ANNs)  have been implemented, and a challenge for better symbolic models has been posed. In  this paper, we present a general-purpose Symbolic Pattern Associator (SPA) based upon  the decision-tree learning algorithm ID3. We conduct extensive head-to-head comparisons  on the generalization ability between ANN models and the SPA under different representations.  We conclude that the SPA generalizes the past tense of unseen verbs better than  ANN models by a wide margin, and we offer insights as to why this should be the case.  We also discuss a new default strategy for decision-tree learning algorithms.  1. Introduction  Learning the past tense of English verbs, a seemingly minor aspect of language acquisition, has generated heated deb...
A Symbolic Model of the Nonconscious Acquisition of Information.
The paper presents counter evidence against Smolensky&#039;s theory that human intuitive  /nonconscious cognitive processes can only be accurately explained in terms  of subsymbolic computations carried out in artificial neural networks. We present  symbolic learning models of two well studied, complicated cognitive tasks involving  nonconscious acquisition of information: learning production rules and artificial finite  state grammars. Our results demonstrate that intuitive learning does not imply  subsymbolic computation, and that the already well-established, perceived correlation  between &#034;conscious&#034; and &#034;symbolic&#034; on the one hand, and between &#034;nonconscious&#034;  and &#034;subsymbolic&#034; on the other, does not exist.
Learning the Past Tense of English Verbs The Symbolic Pattern Associator vs. Connectionist Models.
Learning the past tense of English verbs --- a seemingly minor aspect of language acquisition  --- has generated heated debates since 1986, and has become a landmark task  for testing the adequacy of cognitive modeling. Several artificial neural networks (ANNs)  have been implemented, and a challenge for better symbolic models has been posed. In  this paper, we present a general-purpose Symbolic Pattern Associator (SPA) based upon  the decision-tree learning algorithm ID3. We conduct extensive head-to-head comparisons  on the generalization ability between ANN models and the SPA under different representations.  We conclude that the SPA generalizes the past tense of unseen verbs better than  ANN models by a wide margin, and we offer insights as to why this should be the case.  We also discuss a new default strategy for decision-tree learning algorithms.  1. Introduction  Learning the past tense of English verbs, a seemingly minor aspect of language acquisition, has generated heated deb...
Learning to Control Dynamic Systems with Automatic Quantization.
Learning to control dynamic systems with unknown models is a challenging research  problem. However, most previous work that learns qualitative control rules does not  construct qualitative states --- a proper partition of continuous state variables has to  be designed by human users and given to the learning programs. We design a new  learning method that learns appropriate qualitative state representation and the  control rules simultaneously. Our method can aggressively partition the continuous  state variables into finer, discrete ranges, until control rules based on these ranges are  learned. As a case study, we apply our method to the benchmark control problem of  cart-pole balancing (also known as the inverted pendulum). Experimental results  show that not only does our method derive different partitions for the cart-pole  systems with different parameters, but it also learns to control the systems for an  extended period of time from random initial positions.
Constructive Inductive Logic Programming.
Automating the construction of semantic grammars is a difficult and interesting problem for machine learning. This paper shows how the semantic-grammar acquisition problem can be viewed as the learning of search-control heuristics in a logic program. Appropriate control rules are learned using a new first-order induction algorithm that automatically invents useful syntactic and semantic categories. Empirical results show that the learned parsers generalize well to novel sentences and out-perform previous approaches based on connectionist techniques.  Introduction  Designing computer systems to &#034;understand&#034; natural language input is a difficult task. The laboriously hand-crafted computational grammars supporting natural language applications are often inefficient, incomplete and ambiguous. The difficulty in constructing adequate grammars is an example of the &#034;knowledge acquisition bottleneck&#034; which has motivated much research in machine learning. While numerous researchers have studied ...
A Symbolic Model for Learning the Past%2DTenses of English Verbs.
Supporters of eliminative connectionism have argued for a pattern association based explanation of language learning and language processing. They deny that explicit rules and symbolic representations play any role in language processing and cognition in general. Their argument is based to a large extent on two artificial neural network (ANN) models that are claimed to be able to learn the past tenses of English verbs. (Rumelhart and McClelland, 1986; MacWhinney and Leinbach, 1991). In this article we critically review Rumelhart and McClelland&#039;s as well as MacWhinney and Leinbach&#039;s ANN-models and conclude that they do not succeed in the assigned task of learning the past tenses of English verbs. In order to answer their challenge to the symbolic processing approach, we present our Symbolic Pattern Associator (SPA) -- a general purpose pattern associator  that can learn to associate arbitrary discrete patterns. We carried out several experiments with the SPA using the same set of verbs ...
Inductive Learning from Good Examples.
We study what kind of data may ease the computational complexity of learning of Horn clause theories (in Gold&#039;s paradigm) and Boolean functions (in PAC-learning paradigm). We give several definitions of good data (basic and generative representative sets), and develop data-driven algorithms that learn faster from good examples, and degenerate to learn in the limit from the &#034;worst&#034; possible examples. We show that Horn clause theories, kterm DNF and general DNF Boolean functions are polynomially learnable from generative representative presentations.  1 Introduction  In any inductive learning model, how data of the target theory are supplied to the learning programs is a crucial assumption. Identification in the limit [ Gold, 1967 ] assumes that the series of examples is an admissible enumeration of all (positive and/or negative) examples of the target concept, and requires the learning algorithm to produce a correct hypothesis in some finite  time. However, the computational time and th...
